#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <string.h>

//头结点是在单链表第一个数据节点前附加的‌虚节点‌，‌不存储实际数据元素

typedef int ElemType;

//定义一个单链表的节点结构体
typedef struct Node {
    ElemType data;  //ElemType 是数据类型 ， data是链表中的数据
    struct Node *next;  //定义了指向链表节点的指针
} Node, *LinkList;  //LinkList 是结构体的指针类型

//链表长度
int listLength(LinkList *L) {
    if (L == NULL) return 0;  // 处理空链表头指针情况

    Node *r =  *L;  // 从头节点开始遍历
    int count = 0;
    while (r != NULL) {
        r = r->next;
        count++;
    }
    return count;
}

// 打印链表元素（遍历链表）
void printList(LinkList L) {
    Node *p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}


//初始化
void initList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(Node));  //生成一个节点，为指针地址里面的值开辟空间
    (*L)->next = NULL;  //将指针指向的地址置空
}


//尾部插入元素
void insertEnd(LinkList *L, ElemType n) {
    Node *newNode = (LinkList)malloc(sizeof(Node));
    newNode->data = n;  //将插入的值放到节点的数据域中
    newNode->next = NULL;  //将插入节点的指针置空

    Node *r;
    r=*L;  //将链表的头结点赋值给指针变量里
    while (r->next != NULL) {
        r = r->next;  //更新指针变量的值
    }
    r->next = newNode;  //将原来表中的最后一个节点指针指向空
}

//头部插入元素
void insertFront(LinkList *L,ElemType n){
    Node *newNode = (LinkList)malloc(sizeof(Node));
    newNode->data = n;
    newNode->next = (*L)->next;
    (*L) ->next = newNode;
}

//任意位置插入
void insert(LinkList *L,int pos,ElemType n){
    if(pos<=0 || pos > listLength(L)+1){
        printf("wrong position");
        return;
    }

    Node *newNode = (LinkList)malloc(sizeof(Node));
    newNode->data = n;

    Node *p=*L;
    for (int i = 0; i < pos-1; ++i) {
        p = p->next;
    }

    newNode -> next = p->next;
    p->next=newNode;
}

//任意位置删除元素
void del (LinkList *L,int pos){
    if(*L==NULL||(*L)->next==NULL){
        printf("This is Null.");
    }
    if(pos<=0||pos > listLength(L)+1){
        printf("wrong position");
    }

    Node *p=*L;
    for (int i = 0; i < pos-1; ++i) {
        p=p->next;
    }

    Node *del=p->next;
    p->next = del->next;
    free(del);
    del=NULL;
}

int main() {
    LinkList list;  // 定义链表指针（LinkList = Node*）

    // 初始化链表
    initList(&list);

    // 尾部插入元素
    printf("start1\n");

    insertEnd(&list, 3);
    printList(list);
    insertEnd(&list, 2);
    printList(list);
    insertEnd(&list, 5);
    printList(list);

    printf("end1\n");
    printf("\n");

    //头部插入
    printf("start2\n");

    insertFront(&list,15);
    printList(list);

    printf("end2\n");
    printf("\n");

    //任意位置插入
    printf("start3\n");

    insert(&list,2,45);
    printList(list);

    printf("end3\n");
    printf("\n");


    //任意位置删除
    printf("start4\n");

    del(&list,2);
    printList(list);

    printf("end4\n");
    printf("\n");

    return 0;
}

